package com.yangli.leecode.mashib.interview;

import java.util.Arrays;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/29 13:37
 */
public class SixtySix {
    public static void main(String[] args){

        int[] temp = new int[]{0, 2, 1, 3, 6, 8, 7, 5, 4};
        System.out.println(SixtySix.minValue(temp, 2, 3));
    }


    //最优解 x变0的代价，y是变负数的代价
    public static int minValue(int arr[], int x, int y){
        if (arr == null || arr.length == 0 || x <= 0 || y <= 0) {
            return 0;
        }
        Arrays.sort(arr);
        int n = arr.length;
        for (int l = 0, r = n - 1; l <= r; l++, r--) {//从大到小
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        if (x >= y) {//y代价小，全部是y
            int sum = 0;
            for (int temp : arr) {
                sum = +temp;
            }
            int cost = 0;
            for (int i = 0; i < n && sum > 0; i++) {
                sum -= arr[i] << 1;//相当于减去两倍
                cost += y;
            }
            return cost;
        } else {
            //第一种方式 从i=0位置遍历，默认i之前操作是y操作，后续是x操作直到数据和小于0，枚举所有可能 ==>y操作可能为0个==》ylen ==0  xlen==0 for循环嵌套
            //第二种方式 利用后缀和，快速查找y范围和x范围和无的范围
            for (int i = n - 2; i >= 0; i--) {
                arr[i] += arr[i + 1];
            }
            int benefit = 0;//执行Y操作的收益，一开始没有y操作，收益为0
            int left = mostLeft(arr, 0, benefit);
            int cost = left * x;
            for (int i = 0; i < n - 1; i++) {
                benefit += arr[i] - arr[i + 1];
                left = mostLeft(arr, i + 1, benefit);
                cost = Math.min(cost, (i + 1) * y + (left - i - 1) * x);
            }
            return cost;

        }
    }

    //arr后缀和数据  从l出发，小于等于v的位置返回
    public static int mostLeft(int arr[], int l, int v){
        int r = arr.length - 1;
        int m = 0;
        int ans = arr.length;//没有小于等于的V的值返回n
        while (l <= r) {
            m = (l + r) / 2;
            if (arr[m] <= v) {
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;

    }

    public static int minValue2(int arr[], int x, int y){
        if (arr == null || arr.length == 0 || x <= 0 || y <= 0) {
            return 0;
        }

        return process(arr, 0, x, y, 0);
    }

    public static int process(int arr[], int i, int x, int y, int sum){
        if (i == arr.length) {
            return sum <= 0 ? 0 : Integer.MAX_VALUE;
        }
        int p1 = process(arr, i + 1, x, y, sum + arr[i]);
        int p2 = process(arr, i + 1, x, y, sum);
        if (p2 != Integer.MAX_VALUE) {
            p2 = x + p2;
        }
        int p3 = process(arr, i + 1, x, y, sum - arr[i]);
        if (p3 != Integer.MAX_VALUE) {
            p3 = y + p3;
        }
        return Math.min(p1, Math.min(p2, p3));
    }


}
